"""P5 5.链表"""

"""
HasMap对应python中的dict，HasSet对应python中的set
哈希表增删改查操作的时间复杂度是O(1)，但是常数时间比较大
哈希表的元素是基础类型按值传递，不是基础类型按引用传递

有序表把key按顺序组织起来，哈希表完全不组织
有序表增删改查操作的时间复杂度是O(long(2, N))

题目：
反转单向和双向链表
打印两个有序链表的公共部分
判断一个链表是否为回文结构
将单链表按某值划分成左边小、中间相等、右边大的形式
复制含有随机指针节点的链表

"""


class Node:
    """单向链表节点"""
    def __init__(self, value):
        self.value = value
        self.next = None


def is_palindrome1(head: Node) -> bool:
    """判断一个链表是否为回文结构方法1"""
    if head is None or head.next is None:
        return True
    cur = head
    stack = list()
    # 全部入栈
    while cur:
        stack.append(cur)
        cur = cur.next
    # 出栈比较
    while head:
        if head.value != stack.pop().value:
            return False
        head = head.next
    return True


def is_palindrome2(head: Node) -> bool:
    """判断一个链表是否为回文结构方法2"""
    if head is None or head.next is None:
        return True
    # n1表示中间节点，n2表示末尾节点
    n1 = n2 = head
    while n2.next and n2.next.next:
        n1 = n1.next
        n2 = n2.next.next
    stack = list()
    # 后半段入栈
    while n1:
        stack.append(n1)
        n1 = n1.next
    # 出栈做比较
    while stack:
        if head.value != stack.pop().value:
            return False
        head = head.next
    return True


def is_palindrome3(head: Node) -> bool:
    """判断一个链表是否为回文结构方法3"""
    if head is None or head.next is None:
        return True
    # n1表示中间节点，n2表示末尾节点
    n1 = n2 = head
    while n2.next and n2.next.next:
        n1 = n1.next
        n2 = n2.next.next
    n2 = n1.next
    n1.next = None
    # 反转后半部分
    while n2:
        n3 = n2.next
        n2.next = n1
        n1 = n2
        n2 = n3
    # n2为前半部分，n1、n3为后半部分
    n2 = head
    n3 = n1
    result = True
    while n1 and n2:
        if n1.value != n2.value:
            result = False
            break
        n1 = n1.next
        n2 = n2.next
    # 恢复后半部分
    n1 = n3.next
    n3.next = None
    while n1:
        n2 = n1.next
        n1.next = n3
        n3 = n1
        n1 = n2
    return result


def list_partition(head: Node, pivot: int) -> Node:
    """将单链表按某值划分成左边小、中间相等、右边大的形式"""
    small_head = small_tail = equal_head = \
        equal_tail = big_head = big_tail = None
    while head:
        next_node = head.next
        head.next = None
        if head.value < pivot:
            if small_head is None:
                small_head = small_tail = head
            else:
                small_tail.next = head
                small_tail = head
        elif head.value == pivot:
            if equal_head is None:
                equal_head = equal_tail = head
            else:
                equal_tail.next = head
                equal_tail = head
        else:
            if big_head is None:
                big_head = big_tail = head
            else:
                big_tail.next = head
                big_tail = head
        head = next_node
    if small_tail:
        small_tail.next = equal_head
        equal_tail = equal_tail if equal_tail else small_tail
    if equal_tail:
        equal_tail.next = big_head
    # return small_head if small_head else equal_head if equal_head else big_head
    result = big_head
    if small_head:
        result = small_head
    elif equal_head:
        result = equal_head
    return result


class RandomNode:
    """含有随机指针的节点"""
    def __init__(self, value):
        self.value = value
        self.next = None
        self.random = None


def copy_list_with_rand1(head: RandomNode) -> RandomNode:
    """复制含有随机指针节点的链表方法1"""
    link_map = dict()
    cur = head
    while cur:
        link_map[cur] = RandomNode(cur.value)
        cur = cur.next
    cur = head
    while cur:
        link_map.get(cur).next = link_map.get(cur.next)
        link_map.get(cur).random = link_map.get(cur.random)
        cur = cur.next
    return link_map.get(head)


def copy_list_with_rand2(head: RandomNode) -> RandomNode:
    """复制含有随机指针节点的链表方法2"""
    cur = head
    # 在原链表的每个节点后面添加复制的节点
    while cur:
        next_node = cur.next
        cur.next = RandomNode(cur.value)
        cur.next.next = next_node
        cur = next_node
    cur = head
    # 为复制节点的random赋值
    while cur:
        cur.next.random = cur.random.next if cur.random else None
        cur = cur.next.next
    cur = head
    copy = head.next
    # 分离两条链表
    while cur:
        next_node = cur.next.next
        copy_node = cur.next
        cur.next = next_node
        copy_node.next = next_node.next if next_node else None
        cur = next_node
    return copy


if __name__ == "__main__":
    array = [1, 2, 3, 2, 1]
    # cur_node = array_head = Node(array[0])
    cur_node = array_head = RandomNode(array[0])
    for i in range(1, len(array)):
        # cur_node.next = Node(array[i])
        cur_node.next = RandomNode(array[i])
        cur_node = cur_node.next
    # print(is_palindrome3(array_head))
    # array_head = list_partition(array_head, 1)
    array_head2 = copy_list_with_rand2(array_head)
    while array_head2:
        print(array_head2.value)
        array_head2 = array_head2.next
